package Stack;

public class _42_TrappingRainWater {
    public int trap(int[] height) {
        if(height.length<3) return 0;
        int start = 0, end = height.length - 1;
        int smax = height[start], emax = height[end];
        int count = 0;
        int max = Integer.MIN_VALUE;
        while (start < end) {
            max = Math.max(height[start], height[end]);
            if (max == height[start]) {
                end--;
                if (height[end] < emax) {
                    count += emax - height[end];
                } else {
                    emax = height[end];
                }
            } else {
                start++;
                if (height[start] < smax) {
                    count += smax - height[start];
                } else {
                    smax = height[start];
                }
            }
        }
        return count;
    }
}
